Теорема Вагнера
Минор графа
Определение:
Граф $G'$ — минор графа $G$, если его можно получить из $G$ последовательностью стягиваний ребер и удалений ребер и вершин.
Теорема Вагнера
Формулировка:
Граф $G$ планарен тогда и только тогда, когда у него нет миноров $K_5$ и $K_{3,3}$.
Д-во:
Необходимость очевидна: из правильного изображения $G$ легко получить правильное изображение $G/e$. Достаточность — доказывать не нужно.